package com.itheima.pratice.homeweek;

import java.util.Random;

public class QuiteSort {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int[] arr = new int[100000];
        for(int i = 0;i<100000;i++){
            arr[i] = new Random().nextInt(10000);
        }

        //快排实现
        myQuiteSort(arr,0,arr.length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        long end = System.currentTimeMillis();
        System.out.println("时间为"+(end - start));
    }

    //快排
    public static void myQuiteSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int left0 = left;
        int right0 = right;
        int baseNumber = arr[left];

        while (left != right) {
            while (arr[right] >= baseNumber && right > left) {
                right--;
            }
            while (arr[left] < baseNumber && right > left) {
                left++;
            }
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;
        }
        int temp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = temp;

        myQuiteSort(arr, left0, left - 1);
        myQuiteSort(arr, left + 1, right0);
    }
}
